package max_heap

import (
	"errors"
	"fmt"
)

var (
	ErrMaxHeapIsEmpty = errors.New("MaxHeap is Empty")
)

type MaxHeap struct {
	data []int
}

func (h *MaxHeap) Size() int { return len(h.data) }

func (h *MaxHeap) IsEmpty() bool { return len(h.data) == 0 }

func parent(index int) int {
	if index <= 0 { // 这种逻辑问题在判断调用之前应该避免, 一旦出现, 就该立刻停止程序
		panic("index-0 doesn't has parent node")
	}
	return (index - 1) / 2
}

func leftChild(index int) int { return (index * 2) + 1 }

func rightChild(index int) int { return (index * 2) + 2 }

func (h *MaxHeap) Add(elem int) {
	h.data = append(h.data, elem)
	h.siftUp(len(h.data) - 1)
}

// 上浮操作
func (h *MaxHeap) siftUp(k int) {
	for k > 0 && h.data[k] > h.data[parent(k)] {
		h.data[k], h.data[parent(k)] = h.data[parent(k)], h.data[k]
		k = parent(k)
	}
}

// FindMax 查看堆顶元素
func (h *MaxHeap) FindMax() (int, error) {
	if h.Size() == 0 {
		return -1, ErrMaxHeapIsEmpty
	}
	// 对于最大堆来说, 顶部保持的就是堆中最大的元素
	return h.data[0], nil
}

// ExtractMax 提取最大值, 获取最大堆中的堆顶元素
func (h *MaxHeap) ExtractMax() (int, error) {
	maxElem, err := h.FindMax()
	if err != nil {
		return -1, err
	}
	// 将最后一个元素换到堆顶, 然后删除最后一个元素
	h.data[len(h.data)-1], h.data[0] = h.data[0], h.data[len(h.data)-1]
	h.data = h.data[:len(h.data)-1]
	// 下沉动作
	h.siftDown(0)
	return maxElem, nil
}

// 下沉操作
func (h *MaxHeap) siftDown(k int) {
	// 如果有叶子节点, 需要执行下沉操作
	for leftChild(k) < len(h.data) {

		// j 本轮交换的节点索引
		j := leftChild(k)
		if j+1 <= len(h.data)-1 && h.data[j] < h.data[j+1] {
			j++
		}

		if h.data[k] >= h.data[j] {
			break
		}

		h.data[k], h.data[j] = h.data[j], h.data[k]
		k = j // 更新k节点值, 进入下一轮下沉操作
	}
}

// 堆另外两个经典操作, Heapify 堆化 replace 替换

func (h *MaxHeap) String() string {
	return fmt.Sprintf("MaxHeap: %v\n", h.data)
}

func NewMaxHeap(elems ...int) (*MaxHeap, error) {
	heap := &MaxHeap{
		data: make([]int, 0, len(elems)),
	}

	for _, elem := range elems {
		heap.Add(elem)
	}
	return heap, nil
}
